import java.util.ArrayList;
import java.util.*;

public class Solution {
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        /*
        ArrayList<Integer> res = new ArrayList<>();
        if (input.length == 0 || k == 0) {
            return res;
        }

        Arrays.sort(input);
        for (int i = 0; i < k; i++) {
            res.add(input[i]);
        }

        return res;
        */

        /*
        ArrayList<Integer> res = new ArrayList<>();
        if (k == 0 || input.length == 0 ) {
            return res;
        }

        Queue<Integer> stack = new PriorityQueue<>();
        for (int num : input) {
            stack.add(num);
        }

        while (k-- > 0) {
            res.add(stack.remove());
        }

        return res;
        */

        ArrayList<Integer> res = new ArrayList<>();
        if (k == 0 || input.length == 0) {
            return res;
        } 

        PriorityQueue<Integer> queue = new PriorityQueue<>(
            (o1, o2) -> o2.compareTo(o1)
        );

        for (int i = 0; i < input.length; i++) {
            if (i < k) {
                queue.add(input[i]);
            }
            else {
                if (queue.peek() > input[i]) {
                    queue.remove();
                    queue.add(input[i]);
                }
            }
        }

        while (!queue.isEmpty()) {
            res.add(queue.remove());
        }

        return res;
    }
}